package tree;

/**
 * 路径压缩：p节点的父节点，指向p节点父节点的父节点
 */
public class UnionFind4 implements UF {

    private int[] parent;     //第i个元素指向的根节点
    private int[] rank;       // rank[i] 只能表示一个粗略的rank值，并不能准确的描述节点的高度

    public UnionFind4(int size){
        parent = new int[size];
        rank = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;  //每一个节点都指向自己
            rank[i] = 1;
        }
    }


    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * version3: 合并两个元素的根节点，让 p的根节点指向 q的根节点
     * 时间复杂度：O(h)
     * @param p
     * @param q
     */
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot){
            return;
        }

        // 待合并的两个元素比较rank
        // 将rank低的集合合并到rank高的集合上
        if(rank[pRoot] < rank[qRoot]){
            parent[pRoot] = qRoot;
            //不需要维护rank，因为pRoot的高度一定小于等于qRoot的高度

        }else if(rank[qRoot] < rank[pRoot]){
            rank[qRoot] = pRoot;
        }else {
            //两个元素的rank相等
            parent[qRoot] = pRoot;
            rank[pRoot]  = rank[pRoot] + 1;
        }


    }

    @Override
    public int getSize() {
        return 0;
    }

    // 查找过程，查找元素p所对应的集合编号
    // O(h)复杂度，h为树的高度
    // 查找元素p 的根节点
    // 路径压缩，
    private int find(int p){
        while (p != parent[p]){ // p == parent[p] 表示这个节点是根节点，表示已经遍历完了
            // 路径压缩，让p的父节点，指向p的父节点的父节点
            parent[p] = parent[parent[p]];
            p = parent[p];
        }

        return p;
    }

}
